/*
 * @lc app=leetcode.cn id=738 lang=cpp
 *
 * [738] 单调递增的数字
 */

// @lc code=start
class Solution
{
public:
    int monotoneIncreasingDigits(int n)
    {
        //找出<=0的最大单调递增数
        // n>=0
        //首先肯定是确定最大位 如果不行在回溯
        //上面说的是暴力解法
        //从后往前 因为从前往后第一个数无法判断
        string str = to_string(n);
        int flag = str.size(); //表示从哪里开始赋值9
        for (int i = str.size() - 1; i >= 1; i--)
        {
            //如果不是单调递增
            if (str[i] < str[i - 1])
            {
                str[i - 1]--;
                flag = i;
            }
        }
        //赋值9
        for (int i = flag; i < str.size(); i++)
        {
            str[i] = '9';
        }
        int res = 0;
        for (int i = 0; i < str.size(); i++)
        {
            res *= 10;
            res += str[i] - '0';
        }
        return res;
    }
};
// @lc code=end
